package com.dmall.sort.algorithm;

/**
 * 二分插入排序算法
 * @author xiao1.wang
 * @date 2021/10/7 22:45
 */
@SuppressWarnings("all")
public class BinaryInsertionSort implements Sort {

    @Override
    public void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        binaryInsertionSort(arr, arr.length);
    }

    private void binaryInsertionSort(int[] arr, int n) {
        for (int i = 1; i < n; i++) {
            int value = arr[i];
            int index = binarySearch(arr, i - 1, value);
            int num = i - index;
            switch (num) {
                case 2:  arr[index + 2] = arr[index + 1];
                case 1:  arr[index + 1] = arr[index];
                    break;
                default: System.arraycopy(arr, index, arr, index + 1, num);
            }
            arr[index] = value;
        }
    }

    /**
     * 在数组arr的指定范围[0, r]区间查找第一个大于等于指定target的元素的索引
     * 因为数组的[0, r]索引的数据都是升序的，所以可以根据二分查找
     * 如果target比数组指定区间的所有元素都大
     * @param arr 数组
     * @param r 区间右索引
     * @param target 目标值
     * @return target应该插入到数组的索引
     */
    private int binarySearch(int[] arr, int r, int target) {
        int left = 0;
        int right = r;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                if (mid == 0 || arr[mid - 1] < target) {
                    return mid;
                } else {
                    right = mid - 1;
                }
            }
        }
        return r + 1;
    }

    @Override
    public String getName() {
        return "二分插入排序";
    }

    public static void main(String[] args) {
        int[] arr0 = {1, 2, 3, 3, 3, 3, 4, 5};
        BinaryInsertionSort binaryInsertionSort = new BinaryInsertionSort();
        System.out.println(binaryInsertionSort.binarySearch(arr0, 6, 3));

        int[] arr1 = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        Sort.printArr(arr1);
        Sort sort = new BinaryInsertionSort();
        sort.sort(arr1);
        Sort.printArr(arr1);

        int[] arr2 = {6, 9, 4, 7, 2, 8, 3, 1, 10, 5};
        Sort.printArr(arr2);
        sort.sort(arr2);
        Sort.printArr(arr2);
    }
}
